package com.bo.day20241121;

import java.util.HashMap;
import java.util.HashSet;

/**
 * Dijkstra算法生成最短路径树
 *
 * @Author: gpb
 * @Date: 2024/11/27 16:08
 * @Description:
 */
public class Dijkstra {
    public static HashMap<Node, Integer> dijkstra1 (Node from) {
        // 创建一个HashMap，用于存储从起始节点到其他节点的最短距离
        HashMap<Node, Integer> distanceMap = new HashMap<>();
        // 创一个Set，用于记录已经确定最短距离的节点
        HashSet<Node> selectedNodes = new HashSet<>();
        distanceMap.put(from, 0);
        // 获取距离最短的节点, 并且该节点没有被确定最短距离，不存在selectedNodes里面
        Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        while (minNode != null) {
            //  原始点  ->  minNode(跳转点)   最小距离distance
            Integer integer = distanceMap.get(minNode);
            for (Edge edge : minNode.edges) {
                Node to = edge.to;
                if (!distanceMap.containsKey(to)) {
                    distanceMap.put(to, integer + edge.width);
                } else {
                    distanceMap.put(to, Math.min(distanceMap.get(to), integer + edge.width));
                }
            }
            selectedNodes.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        }
        return distanceMap;
    }

    /**
     * 获取距离最短的节点, 并且该节点没有被确定最短距离，不存在selectedNodes里面。返回
     *
     * @param distanceMap
     * @param selectedNodes
     * @return
     */
    private static Node getMinDistanceAndUnselectedNode (HashMap<Node, Integer> distanceMap, HashSet<Node> selectedNodes) {
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for (Node node : distanceMap.keySet()) {
            if (!selectedNodes.contains(node) && distanceMap.get(node) < minDistance) {
                minNode = node;
                minDistance = distanceMap.get(node);
            }
        }
        return minNode;
    }
}
